package com.leetcode.贪心;

/**
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 * @author LZF
 *
 */
public class L134加油站 {
	public static void main(String[] args) {
		int[] gas = {1,2,3,4,5};
		int[] cost = {3,4,5,1,2};
		System.out.println(canCompleteCircuit(gas, cost));
	}
	/**
	 * 情况一：如果gas的总量小于cost的总量，则不管从哪里出发，都不能走一周
	 * 情况二：如果rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，
	 * 		如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
	 * 情况三：如果累加的最小值min是负数，说明从0出发不能走一圈。
	 * 如果从0之前的某一个点i作为起点，rest[i] = gas[i]-cost[i]，为这一个剩下的油量
	 * 因为i肯定会经过0，那么累加的最小值min就变为min = min + rest[i],如果此时min>=0，那么i就是起点，如果还是小于0，就继续判断i-1
	 */
	public static int canCompleteCircuit(int[] gas, int[] cost) {
		int min = Integer.MAX_VALUE;
		int volume = 0;
		for(int i = 0;i < gas.length;i++) {
			volume += gas[i] - cost[i];
			min = Math.min(min,volume);
		}
		if(volume < 0) return -1;//情况一
		if(min >= 0) return 0;//情况二
		//情况三
		for(int i = gas.length - 1;i >= 0;i--) {
			min += gas[i] - cost[i];
			if(min >= 0) return i;
		}
		return -1;
    }
    //贪心的第二种解法见代码随想录
}
